/*
 * @lc app=leetcode.cn id=41 lang=javascript
 *
 * [41] 缺失的第一个正数
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */

// 时间复杂度超出
// var firstMissingPositive = function(nums) {
//   let min = 0;
//   nums.sort((a,b)=>a -b);
//   for (let i = 0; i < nums.length; i++) {
//     if(nums[i] > 0 && nums[i] === min + 1){
//       min = nums[i]
//     }
//   }
//   return min + 1;
// };

// 空间大小超标
// 把元素值放到数组对应下标位减1位置
// var firstMissingPositive = function(nums) {
//   let arr = [];
//   for (let i = 0; i < nums.length; i++) {
//     if(nums[i] <= 0 || nums[i] > nums.length) continue;
//     if(arr[nums[i] - 1] !== nums[i]){
//       arr[nums[i] - 1] = nums[i];
//     }
//   }
//   for (let i = 0; i < arr.length; i++) {
//     if(arr[i] != i + 1) return i + 1;
//   }
//   return arr.length + 1;
// };

var firstMissingPositive = function(nums) {
  /**
   * 不开辟额外空间，将nums各位放至对应为位置
   * nums[i] 放到 nums[nums[i] - 1] 位置
   */
  
  // 对位置进行遍历，是所有位置都放置对一个值
  for (let i = 0; i < nums.length; i++) {
    // 如果nums[i] 不在对应为位置
    while(nums[i] !== i + 1){
      if(nums[i] <= 0 || nums[i] > nums.length) break;

      // 找到nums[i] 应该在的位置
      let ind = nums[i] - 1;
      if(nums[ind] === nums[i]) break;
      // 和该位置对换，则nums[i]放到了对应位置
      [nums[i], nums[ind]] = [nums[ind], nums[i]];
    }
  }

  let ind = 0;
  while(nums[ind] === ind + 1 && ind < nums.length) ind++;
  return ind + 1;
}
// @lc code=end

